﻿#include <iostream>
#include <vector>
using namespace std;
void search_last(vector<int>& arr,int& cur,int& dest) {
    
    int n = arr.size();
    while (cur < n) { // 外层循环应用cur控制
        if (arr[cur] == 0) {          
            dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        else {            
            dest++;
            if (dest >= n - 1) break;
            cur++;
        }
        
    }
    // 处理边界情况
    if (dest == arr.size()) {
        arr[arr.size() - 1] = 0;
        dest -= 2;
        cur--;
    }
       
}

class Solution {
public:
    void static duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        // 1.先找最后一个被操作元素的下标

        search_last(arr, cur, dest);//2.函数中要处理边界情况
        
        // 3. 从后向前完成复写操作 

        while (cur >= 0) {
            if (arr[cur] == 0) {// dest先向后移动一位
                int i = 2;
                while (i--) {
                    if (dest <= 0)  break;
                    arr[dest--] = 0;
                }
            }
            else {// 将arr[cur]的值给arr[dest] dest向后移动一位
                if (dest <= 0)  break;
                arr[dest--] = arr[cur];
            }
            cur--;
        }
        
    }
};
   

int main() {
    vector <int> vcr = { 8,4,5,0,0,0,0,7 };
    Solution::duplicateZeros(vcr);
}